Confidence%2DBased Feature Acquisition to Minimize Training and Test Costs.

Progressive refinement for support vector machines.

Modelling and learning user preferences over sets.

K%2Dmeans in space a radiation sensitivity evaluation.
Spacecraft increasingly employ onboard data analysis to inform further data collection and prioritization decisions. However, many spacecraft operate in high-radiation environments in which the reliability of dataintensive computation is not known. This paper presents the first study of radiation sensitivity for k-means clustering. Our key findings are 1) k-means data structures differ in sensitivity, which is not determined solely by the amount of memory exposed; 2) no special radiation protection is needed below a dataset-dependent radiation threshold, enabling the use of faster, smaller, and cheaper onboard memory; and 3) subsampling improves radiation tolerance slightly, but the use of kdtrees unfortunately reduces tolerance. Our conclusions can help tailor k-means for use in future high-radiation environments. 1.
AAAI 2008 Workshop Reports.

Multiple%2DInstance Regression with Structured Data.

On%2Dboard analysis of uncalibrated data for a spacecraft at mars.

Report on the SIGART Doctoral Consortium.

When Is Constrained Clustering Beneficial%2C and Why%3F.
Several researchers have illustrated that constraints can improve the results of a variety of clustering algorithms. However, there can be a large variation in this improvement, even for a fixed number of constraints for a given data set. We present the first attempt to provide insight into this phenomenon by characterizing two constraint set properties: inconsistency and incoherence. We show that these measures are strongly anti-correlated with clustering algorithm performance. Since they can be computed prior to clustering, these measures can aid in deciding which constraints to use in practice.
Active Learning with Irrelevant Examples.
Abstract. Active learning algorithms attempt to accelerate the learning process by requesting labels for the most informative items first. In real-world problems, however, there may exist unlabeled items that are irrelevant to the user’s classification goals. Queries about these points slow down learning because they provide no information about the problem of interest. We have observed that when irrelevant items are present, active learning can perform worse than random selection, requiring more time (queries) to achieve the same level of accuracy. Therefore, we propose a novel approach, Relevance Bias, in which the active learner combines its default selection heuristic with the output of a simultaneously trained relevance classifier to favor items that are likely to be both informative and relevant. In our experiments on a real-world problem and two benchmark datasets, the Relevance Bias approach significantly improved the learning rate of three different active learning approaches. 1
Learning user preferences for sets of objects.
Most work on preference learning has focused on pairwise preferences or rankings over individual items. In this paper, we present a method for learning preferences over sets of items. Our learning method takes as input a collection of positive examples—that is, one or more sets that have been identified by a user as desirable. Kernel density estimation is used to estimate the value function for individual items, and the desired set diversity is estimated from the average set diversity observed in the collection. Since this is a new learning problem, we introduce a new evaluation methodology and evaluate the learning method on two data collections: synthetic blocks-world data and a new real-world music data collection that we have gathered. 1.
Value%2C Cost%2C and Sharing Open Issues in Constrained Clustering.
Clustering is an important tool for data mining, since it can  identify major patterns or trends without any supervision (labeled data).
Measuring Constraint%2DSet Utility for Partitional Clustering Algorithms.
Abstract. Clustering with constraints is an active area of machine learning and data mining research. Previous empirical work has convincingly shown that adding constraints to clustering improves the performance of a variety of algorithms. However, in most of these experiments, results are averaged over different randomly chosen constraint sets from a given set of labels, thereby masking interesting properties of individual sets. We demonstrate that constraint sets vary significantly in how useful they are for constrained clustering; some constraint sets can actually decrease algorithm performance. We create two quantitative measures, informativeness and coherence, that can be used to identify useful constraint sets. We show that these measures can also help explain differences in performance for four particular constrained clustering algorithms. 1
The 2005 SIGART%2FAAAI Doctoral Consortium.


DD%2DPREF A Language for Expressing Preferences over Sets.
In many application domains, it is useful to be able to represent and reason about a user’s preferences over sets of objects. We present a representation language, DD-PREF (for Diversity and Depth PREFerences), for specifying the desired diversity and depth of sets of objects where each object is represented as a vector of feature values. A strong diversity preference for a particular feature indicates that the user would like the set to include objects whose values are evenly dispersed across the range of possible values for that feature. A strong depth preference for a feature indicates that the user is interested in specific target values or ranges. Diversity and depth are complementary, but are not necessarily opposites. We define an objective function that, when maximized, identifies the subset of objects that best satisfies a statement of preferences in DD-PREF. Exhaustively searching the space of all possible subsets is intractable for large problem spaces; therefore, we also present an efficient greedy algorithm for generating preferred object subsets. We demonstrate the expressive power of DD-PREF and the performance of our greedy algorithm by encoding and applying qualitatively different preferences for multiple tasks on a blocks world data set. Finally, we provide experimental results for a collection of Mars rover images, demonstrating that we can successfully capture individual preferences of different users, and use them to retrieve high-quality image subsets.



Mining GPS Traces for Map Refinement.

Constrained K%2Dmeans Clustering with Background Knowledge.
Clustering is traditionally viewed as an unsupervised method for data analysis. However, in some cases information about the problem domain is available in addition to the data instances themselves. In this paper, we demonstrate how the popular k-means clustering algorithm can be pro tably modi- ed to make use of this information. In experiments with arti cial constraints on six data sets, we observe improvements in clustering accuracy. We also apply this method to the real-world problem of automatically detecting road lanes from GPS data and observe dramatic increases in performance. 1.
Clustering with Instance%2DLevel Constraints.
Clustering algorithms conduct a search through the space of possible organizations of a data set. In this paper, we propose two types of instance-level clustering constraints - must-link and cannot-link constraints - and show how they can be incorporated into a clustering algorithm to aid that search. For three of the four data sets tested, our results indicate that the incorporation of surprisingly few such constraints can increase clustering accuracy while decreasing runtime. We also investigate the relative effects of each type of constraint and find that the type that contributes most to accuracy improvements depends on the behavior of the clustering algorithm without constraints.
Generalized clustering%2C supervised learning%2C and data assignment.
Clustering algorithms have become increasingly important in handling and analyzing data. Considerable work has been done in devising effective but increasingly specific clustering algorithms. In contrast, we have developed a generalized framework that accommodates diverse clustering algorithms in a systematic way. This framework views clustering as a general process of iterative optimization that includes modules for supervised learning and instance assignment. This framework has also suggested several novel clustering methods. In this paper, we investigate experimentally the efficacy of these algorithms and test some hypotheses about the relation between such unsupervised techniques and the supervised methods embedded in them.
Clustering with Instance%2DLevel Constraints.
Clustering algorithms conduct a search through the space of possible organizations of a data set. In this paper, we propose two types of instance-level clustering constraints - must-link and cannot-link constraints - and show how they can be incorporated into a clustering algorithm to aid that search. For three of the four data sets tested, our results indicate that the incorporation of surprisingly few such constraints can increase clustering accuracy while decreasing runtime. We also investigate the relative effects of each type of constraint and find that the type that contributes most to accuracy improvements depends on the behavior of the clustering algorithm without constraints.
Refining Inductive Bias in Unsupervised Learning via Constraints.

Refining Inductive Bias in Unsupervised Learning via Constraints.

Clustering with Instance%2Dlevel Constraints.
Clustering algorithms conduct a search through the space of possible organizations of a data set. In this paper, we propose two types of instance-level clustering constraints - must-link and cannot-link constraints - and show how they can be incorporated into a clustering algorithm to aid that search. For three of the four data sets tested, our results indicate that the incorporation of surprisingly few such constraints can increase clustering accuracy while decreasing runtime. We also investigate the relative effects of each type of constraint and find that the type that contributes most to accuracy improvements depends on the behavior of the clustering algorithm without constraints.
Alpha seeding for support vector machines.
A key practical obstacle in applying support vector machines to many large-scale data mining tasks is that SVM’s generally scale quadratically (or worse) in the number of examples or support vectors. This complexity is further compounded when a specific SVM training is but one of many, such as in Leave-One-Out-Cross-Validation (LOOCV) for determining optimal SVM kernel parameters or as in wrapper-based feature selection. In this paper we explore new techniques for reducing the amortized cost of each such SVM training, by seeding successive SVM trainings with the results of previous similar trainings. 1
